//创建一个链表（单链表）并实现方法
struct ListNode
{
    int val;
    ListNode* next;
    ListNode():val(0),next(nullptr){}
    ListNode(int x):val(x),next(nullptr){}
    ListNode(int x,ListNode* next):val(x),next(next){}
};
//这里的head结点视为有元素，故设置一个虚拟头结点

//列表插入
ListNode* Insert(int val, ListNode* head)
{
    ListNode* cur;
    cur->next=head;
    while(cur->next!=nullptr)
        cur=cur->next;
    cur->next=new ListNode(val);
    return head;

}


//删除尾部节点
ListNode* Delete(ListNode* head)
{
    if(head==nullptr)   return nullptr;
    ListNode* dummyhead;
    dummyhead->next=head;
    ListNode* cur=dummyhead;
    while(cur->next->next!=nullptr)
        cur=cur->next;
    cur->next=nullptr;
    return dummyhead->next;
}


//删除第n个结点
bool Delete_n(ListNode* head,int n)
{
    ListNode* cur;
    cur->next=head;
    for(int i=0;i<n-1;i++)
    {
        if(cur->next==nullptr)  return false; 
        cur=cur->next;  
        //最终要指向第n-1个
    }
    ListNode* temp;
    temp=cur->next;
    cur->next=cur->next->next;
    delete temp;
    return true;
}


//插入结点到第n个前
bool Insert_n(ListNode* head ,int n,int val)
{
    ListNode* cur;
    cur->next=head;
    for(int i=0;i<n-1;i++)
    {
        if(!cur) return false;
        cur=cur->next;
    }
    ListNode* newNode=new ListNode(val);
    newNode->next=cur->next->next;
    cur->next=newNode;
    return true;
}

//寻找元素val
bool Search_val(ListNode* head,int val)
{
    
    ListNode* cur;
    cur->next=head;
    while(cur->next)
    {
        if(cur->next->val==val) return true;
        cur=cur->next;
    }
    return false;
}



//寻找第n个元素
int Search_n(ListNode* head,int n)
{
    ListNode* cur;
    cur->next=head;
    for(int i=0;i<n-1;i++)
    {
        if(!cur) return false;
        cur=cur->next;
    }
    return cur->next->val;
}
